#pragma once

//结点结构
template <typename E>
struct LNode
{
    E data;//数据域
    LNode *next;//指针域
};
//链表类型
//typedef LNode *LinkList; //for c
template <typename E>
using LinkList = LNode<E> *;//for c++
//初始化链表为空表 InitList(&L)
template <typename E>
void InitList(LinkList<E> &L)
{
    L=new LNode<E>;
    L->next = nullptr;
}
//链表插入 ListInsert(&L,i,e)
template<typename E>
void ListInsert(LinkList<E> &L, int i, E e)
{
    //查找第i-1个结点 p
    auto p = L;
    int j = 0;
    while (p && j < i-1){
        p = p->next;
        ++j;
    }
    //若p存在，在其后插入e
    if (p && j==i-1){
        //新建结点 ，保存e
        auto s= new LNode<E>;
        s->data =e;
        //在p之后插入s
        s->next =p->next;
        p->next =s;
    }else {
        throw "Invalid i";
    }
}
//链表删除 ListDelete(&L,i,&e)
template <typename E>
void ListDelete(LinkList<E> &L,int i, E e)
{
    //查找第i-1个结点 p
    auto p = L;
    int j = 0;
    while (p && j < i-1){
        p = p->next;
        ++j;
    }
    //若第 i个结点存在，则删除
    if (p &&j==i-1 && p->next){
        //取出元素，用e返回
        auto q=p->next;
        e=q->data;
        //删除第i个结点 q
        p->next =q->next;
        delete q;

    } else {
        throw "Invalid i";
    
    }
}
    
